/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: dings
 * Date: 2024-07-21
 * Time: 22:52
 */
public class Test {
    /**
     * 冒泡排序(含boolean变量和-i优化)
     * 时间复杂度：【讨论没有优化的情况下，也就是 没有下方的boolean元素和-i操作】O（N^2）
     * 优化后的时间复杂度会达到O（N） （第一趟就排好序了）
     * 空间复杂度：O(1)
     * @param arr
     */
    public void bubble(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j]>arr[j+1]) {
                    swap(arr,j,j+1);
                    flg = true;
                }
            }
            if (!flg) {
                break;
            }
        }
    }
}
